今天一次寫了三題 interval 相關題目。

解 interval 類型題的思路

解題前，腦中有以下圖示來幫助理解兩兩區間（如 {s1, e1} 和 {s2, e2}）是否重疊。

首先，確保區間1 的開始(s1)會小於等於 區間2的開始 (s2)，此時，兩個區間只有 2 種重疊樣子(如下)，重疊情況都能歸納成 s2 > e1。

  s1         e1         s1    e1
  |-----------|         |------|
    |-----|               |-------|
    s2    e2              s2      e1  
  

其餘情況: e1 >= s2 也就會是非交疊的狀態。

   s1   e1
    |---|
          |----|
          s2   e2

56. Merge Intervals (medium)

題目:
給一個區間二維陣列 intervals，其中 intervals[i] = [starti, endi]，合併所有重疊區間，並傳回覆蓋輸入中所有區間的非重疊區間數組。

解題思路:
首先排序所有區間，接著迭代所有區間，對兩兩比較區間 (我視兩區間為 被比較區間(s1 e1) 與 比較區間(s2 e2))，如果沒有重疊（s2 > e），將被比較的區間加入答案陣列，並此區間更新為被比較區間 ({s, e})。如果有重疊，則取兩區間最大上下界。迭代結束後，將最後一個區間加入結果答案陣列，因為最後一個區間無法在循環中處理。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> res;
        sort(intervals.begin(), intervals.end()); // Sort intervals based on their starting points
        int s = intervals[0][0], e = intervals[0][1]; // Initialize with the first interval
        
        for (int i = 1; i < intervals.size(); i++) {
            int s2 = intervals[i][0], e2 = intervals[i][1];
            if (s2 > e) {  // If no overlap, add the previous interval to the result
                res.push_back({s, e});
                s = s2;  // Update to the current interval
                e = e2;
            } else {  // If overlapping, merge the intervals
                e = max(e, e2);
            }
        }
        res.push_back({s, e}); // Add the last interval to the result
        return res;
    }
};

57. Insert Interval (Medium)

給一個沒有重疊區間並且都以開始時間做遞增排序的二維陣列 intervals，和一個區間陣列 newInterval。返回一個插入 newInterval後，仍保持沒有重疊區間(可做 merge)且遞增排序的 intervals。

解題想法:
上一題，在迭代中，被比較的區間會不斷換下一個。而此題被比較的區間是固定的，因此無法把在發現重疊區間後，找到好時機將合併的區間在塞進答案陣列中。

此題我的做法為迭代中會將原本陣列分成三部分

[重疊區間前] [重疊區間，需合併] [重疊區間後]

迭代後合併成答案。

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> left, right;
        int s = newInterval[0], e = newInterval[1];
        for (int i = 0; i < intervals.size(); i++) {
            int s2 = intervals[i][0], e2 = intervals[i][1];
            if (e2 < s) {
                left.push_back({s2, e2});
            }else if (s2 > e){
                right.push_back({s2, e2});
            }else {
                s = min(s, s2);
                e = max(e, e2);
            }
        }
        // Combine left, the merged new interval, and right
        vector<vector<int>> result = left;
        result.push_back({s, e});
        result.insert(result.end(), right.begin(), right.end());
        return result;
    }
};

435. Non-overlapping Intervals (Medium)

題目敘述:
給一個包含多個區間的陣列 intervals，返回移除最少移除區間數，使剩餘 intervals沒有重疊的區間

解題
首先，根據區間開始時間做遞增排序。然後遍歷每個區間做兩兩比較，若兩個區間無重疊，則將當前區間更新為比較的區間；若有重疊，則移除結束時間較晚的區間 (ctr++)，這樣能盡可能減少影響。

經過寫第10天寫 Maximum Number of Events That Can Be Attended後，我好像比較有抓到 Greedy的感覺

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int s = intervals[0][0], e = intervals[0][1];
        int ctr = 0;
        for (int i = 1; i < intervals.size(); i++) {
            int s2 = intervals[i][0], e2 = intervals[i][1];
            if (s2 >= e) {
                s = s2, e = e2;
                continue;
            } 
            // remove the interval with latter end
            ctr += 1;
            if (e2 < e) {
                s = s2, e = e2; 
            }

        }
        return ctr;
    }
};

這 30 天的回顧:

30 天寫 一日至少寫一題 leetcode 題，發現自己有培養寫 leetcode 題的習慣，當我逃避寫論文時就會來刷 leetcode (誤
這報名這系列，最初是想要順便練習 Rust，所以將 Rust 這語言寫在主題裡，然而我這 30 天只有寫了 2 天的 Rust。因此我接下來就繼續學更多 leetcode 技巧(如 math 解法、BIT..等)與練習更多的 rust 題。